package problem112;

//112.路径总和
//https://leetcode.cn/problems/path-sum/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPath(root, 0, targetSum);
    }
    public boolean hasPath(TreeNode root, int sum, int targetSum) {
        if(root == null) return false;
        sum += root.val;
        if(sum == targetSum && root.left == null && root.right == null) return true;

        if(hasPath(root.left, sum, targetSum)) return true;
        if(hasPath(root.right, sum, targetSum)) return true;

        return false;
    }
}